翻訳と辞書 Words near each other ・ Quadrula refulgens ・ Quadrula rumphiana ・ Quadrula tuberosa ・ Quadrumana ・ Quadratic integrate and fire ・ Quadratic irrational ・ Quadratic Jordan algebra ・ Quadratic Lie algebra ・ Quadratic mean diameter ・ Quadratic pair ・ Quadratic probing ・ Quadratic programming ・ Quadratic reciprocity ・ Quadratic residue ・ Quadratic residue code ・ Quadratic residuosity problem ・ Quadratic set ・ Quadratic sieve ・ Quadratic transformation ・ Quadratic unconstrained binary optimization ・ Quadratic variation ・ Quadratic-linear algebra ・ Quadratically closed field ・ Quadratically constrained quadratic program ・ Quadratics ・ Quadratini ・ Quadratino ・ Quadrato di Villafranca ・ Quadratojugal bone ・ Quadratrix Dictionary Lists mini英和辞書 mini和英辞書 Webster 1913 Latin-English FOLDOC Wikipedia English ウィキペディア

翻訳と辞書　辞書検索 [ 開発暫定版 ] スポンサード リンク Quadratic residuosity problem ： ウィキペディア英語版 Quadratic residuosity problem The quadratic residuosity problem in computational number theory is to decide, given integers $a$ and $N$, whether $a$ is a quadratic residue modulo $N$ or not. Here $N\; =\; p\_1\; p\_2$ for two unknown primes $p\_1$ and $p\_2$, and $a$ is among the numbers which are not obviously quadratic non-residues (see below). The problem was first described by Gauss in his ''Disquisitiones Arithmeticae'' in 1801. This problem is believed to be computationally difficult. Several cryptographic methods rely on its hardness, see Applications. An efficient algorithm for the quadratic residuosity problem immediately implies efficient algorithms for other number theoretic problems, such as deciding whether a composite $N$ of unknown factorization is the product of 2 or 3 primes . == Precise formulation == Given integers $a$ and $T$, $a$ is said to be a ''quadratic residue modulo $T$'' if there exists an integer $b$ such that :$a\; \backslash equiv\; b^2\; \backslash pmod\; T$. Otherwise we say it is a quadratic non-residue. When $T\; =\; p$ is a prime, it is customary to use the Legendre symbol: :$\backslash left(\backslash frac\backslash right)\; =$ \begin 1 & \text a \text p \text a \not\equiv 0\pmod, \\ -1 & \text a \text p, \\ 0 & \text a \equiv 0 \pmod. \end This is a multiplicative character which means $\backslash big(\backslash tfrac\backslash big)\; =\; 1$ for exactly $(p-1)/2$ of the values $1,\backslash ldots,p-1$, and it is $-1$ for the remaining. It is easy to compute using the law of quadratic reciprocity in a manner akin to the Euclidean algorithm, see Legendre symbol. Consider now some given $N\; =\; p\_1\; p\_2$ where $p\_1$ and $p\_2$ are two, different unknown primes. A given $a$ is a quadratic residue modulo $N$ if and only if $a$ is a quadratic residue modulo both $p\_1$ and $p\_2$. Since we don't know $p\_1$ or $p\_2$, we cannot compute $\backslash big(\backslash tfrac\backslash big)$ and $\backslash big(\backslash tfrac\backslash big)$. Perhaps surprisingly, however, we can easily compute their product! This is known as the Jacobi symbol: :$$ \left(\frac\right) = \left(\frac\right)\left(\frac\right) This can also be efficiently computed using the law of quadratic reciprocity for Jacobi symbols. However, $\backslash big(\backslash tfrac\backslash big)$ can not in all cases tell us whether $a$ is a quadratic residue modulo $N$ or not! More precisely, if $\backslash big(\backslash tfrac\backslash big)\; =\; -1$ then $a$ is necessarily a quadratic non-residue modulo either $p\_1$ or $p\_2$, in which case we are done. But if $\backslash big(\backslash tfrac\backslash big)\; =\; 1$ then it is either the case that $a$ is a quadratic residue modulo both $p\_1$ and $p\_2$, or a quadratic non-residue modulo both $p\_1$ and $p\_2$. We cannot distinguish these cases from knowing just that $\backslash big(\backslash tfrac\backslash big)\; =\; 1$. This leads to the precise formulation of the quadratic residue problem: Problem: Given integers $a$ and $N\; =\; p\_1\; p\_2$, where $p\_1$ and $p\_2$ are unknown, different primes, and where $\backslash big(\backslash tfrac\backslash big)\; =\; 1$, determine whether $a$ is a quadratic residue modulo $N$ or not. 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Quadratic residuosity problem」の詳細全文を読む スポンサード リンク 翻訳と辞書 : 翻訳のためのインターネットリソース Copyright(C) kotoba.ne.jp 1997-2016. All Rights Reserved.